package com.atguigu.linklist;

import java.util.Stack;
class ListNode{
    int val;
    ListNode random;
    ListNode next;
    public ListNode(int val){
        this.val=val;
    }
}
public class ParadolinList {
    public static void main(String[] args) {
        ListNode head=new ListNode(1);
        head.next=new ListNode(0);
        head.next.next=new ListNode(0);
        System.out.println(isPalindrome2(head));
    }
    public static boolean isPalindrome1(Node head){
        //压栈形式
        Stack<Integer> stack=new Stack<>();
        if(head==null || head.next==null){
            return true;
        }
        Node cur=head;
        while(cur!=null){
            stack.push(cur.val);
            cur=cur.next;
        }
        while(head!=null){
            if(head.val!=stack.peek()){
                return false;
            }else{
                stack.pop();
                head=head.next;
            }
        }
        if(!stack.isEmpty()){
            return false;
        }
        return true;
    }
    public static boolean isPalindrome2(ListNode head){
        if(head==null || head.next==null){
            return true;
        }
        ListNode fast=head;
        ListNode slow=head;
        //快指针一次两步，慢指针一次一步
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //此时慢指针指向中点位置，反转慢指针及其之后
        ListNode cur=slow.next;
        slow.next=null;
        while(cur!=null){
            ListNode node=cur.next;
            cur.next=slow;
            slow=cur;
            cur=node;
        }
        while(slow!=null && head!=null){
            if(slow.val!=head.val){
                return false;
            }
            slow=slow.next;
            head=head.next;
        }
        return true;
    }
}
